﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Analysis_Sorting_Algorithms
{
    class QuickSort
    {
        public  int[]  sortIt(int[] array, int left, int right, ref int compare)
        {

            int sortingIndex = Sorting(array, left, right, ref compare);

            //if sorting still needs to be done created two new sublists

            if (sortingIndex - 1 > left + 1) // if false then sub list would be of size 0 or 1 and therefore sorted
            {
                sortIt(array, left, sortingIndex - 1, ref compare);
            }

            if (sortingIndex < right - 1) //if false then sub list would be of size 0 or 1 and therefore sorted
            {
                sortIt(array, sortingIndex, right, ref compare);
            }
            return array;
        }

        private int Sorting(int[] array, int left, int right, ref int compare)
        {
            Random rand = new Random();
            int newLeft = left;
            int newRight = right;
            int pivot = array[left + rand.Next(right - left + 1)]; //picking a random pivot in range

            while (newLeft <= newRight) // while still in bounds of the sub array
            {
                while (array[newLeft] < pivot) // element value is less than mid point so skip
                {
                    compare++;
                    newLeft++;
                    
                }

                while (array[newRight] > pivot) //element is greater than mid point so skipp
                {
                    compare++;
                    newRight--;
                }

                if (newLeft <= newRight) // left and right 'pointer' are still inside their respective sublists 
                {
                    //swap values at left and right 
                    int tmpHolder = array[newLeft];
                    array[newLeft] = array [newRight];
                    array[newRight] = tmpHolder;
                    //left and right are in there place at least for the moment so shift both 'pointers' closer to the middle
                    newLeft++;
                    newRight--;
                    compare++;
                }
            }
            return newLeft;
        }
    }
}
